#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/7 15:54
# @USER    : Shengji He
# @File    : ReverseNodesKGroup.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reverse(self, head: ListNode, tail: ListNode):
        """
        翻转一个子链表，并且返回新的头与尾
        :param head: ListNode
        :param tail: ListNode
        :return:
        """
        prev = tail.next
        p = head
        while prev != tail:
            nex = p.next
            p.next = prev
            prev = p
            p = nex
        return tail, head

    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        """
        Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

        k is a positive integer and is less than or equal to the length of the linked list.
        If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

        Example:

        Given this linked list: 1->2->3->4->5

        For k = 2, you should return: 2->1->4->3->5

        For k = 3, you should return: 3->2->1->4->5

        Note:

        Only constant extra memory is allowed.
        You may not alter the values in the list's nodes, only nodes itself may be changed.

        :param head: ListNode
        :param k: int
        :return: ListNode
        """
        # if k < 2 or not head or not head.next:
        #     return head
        # node = ListNode(0)
        # ans = copy.deepcopy(head)
        #
        # for i in range(k):
        #     if head:
        #         # rem.next = rem
        #         temp = ListNode(0)
        #         temp.next = head
        #
        #         head = head.next
        #
        #         temp.next.next = node.next
        #         node = temp
        #
        #     else:
        #         return ans
        # ans = node.next
        # while node.next:
        #     node = node.next
        # node.next = self.reverseKGroup(head, k)
        # return ans
        hair = ListNode(0)
        hair.next = head
        pre = hair
        while head:
            tail = pre
            # 查看剩余部分长度是否大于等于 k
            for i in range(k):
                tail = tail.next
                if not tail:
                    return hair.next
            nex = tail.next
            head, tail = self.reverse(head, tail)
            # 把子链表重新接回原链表
            pre.next = head
            tail.next = nex
            pre = tail
            head = tail.next
        return hair.next


if __name__ == '__main__':
    S = Solution()
    # input1 = [1, 2, 3, 4, 5]
    input1 = [1, 2, 3, 4, 5]
    k = 3
    # input1 = [1]
    print(input1)
    l1 = ListNode(input1.pop(0))
    temp1 = l1
    for element in input1:
        temp1.next = ListNode(element)
        temp1 = temp1.next
    output = S.reverseKGroup(l1, k)
    print('done')
